/**
 * 取出一个任务
 */
export function peek(queue: any) {
  return queue.length !== 0 ? queue[0] : null;
}
/**
 * 推入一个任务
 */
export function push(queue: any, task: any) {
  const index = queue.length;
  queue.push(task);

  // 向上调整
  shiftUp(queue, task, index);
}

/**
 * 弹出一个任务
 */
export function pop(queue: any) {
  if (queue.length === 0) {
    return null;
  }

  const first = queue[0];
  const last = queue.pop();

  // 证明队列中只有一个任务
  if (last === first) {
    return;
  }

  queue[0] = last;
  shiftDown(queue, last, 0);
}

/**
 * 向上调整
 */
function shiftUp(heap: any, task: any, index: number) {
  while (index > 0) {
    // 父节点的索引
    const parentIndex = (index - 1) >>> 1;
    const parentTask = heap[parentIndex];

    // 如果当前任务与父任务的差值小于0，证明当前任务优先级更高，则交换位置
    if (compare(task, parentTask) < 0) {
      heap[index] = parentTask;
      heap[parentIndex] = task;
      index = parentIndex;
    } else {
      return;
    }
  }
}

function shiftDown(heap: any, task: any, index: number) {
  // 得到数组长度
  const len = heap.length;
  // 得到数组长度的一半
  const halfLen = len >>> 1;

  // 防止越界
  while (index < halfLen) {
    // 得到左子节点的 index
    const leftIndex = index * 2 + 1;

    // 得到右子节点的 index
    const rightIndex = index * 2 + 2;

    // 当前节点与左子节点进行比较
    // 若左子节点对比不成功，则比较右子节点
    // 若前面两层都不成功，则当前节点就是最小值
    // rightIndex < len 为了防止没有右节点
    if (compare(task, heap[leftIndex]) < 0) {
      // 此时还需将左节点与右节点进行比较
      if (compare(heap[leftIndex], heap[rightIndex]) < 0 && rightIndex < len) {
        heap[index] = heap[leftIndex];
        heap[leftIndex] = task;
        index = leftIndex;
      } else {
        heap[index] = heap[rightIndex];
        heap[rightIndex] = task;
        index = rightIndex;
      }
    } else if (compare(task, heap[rightIndex]) < 0 && rightIndex < len) {
      heap[index] = heap[rightIndex];
      heap[rightIndex] = task;
      index = rightIndex;
    } else {
      return;
    }
  }
}

/**
 * 计算两个任务优先级的差值
 */
function compare(a: any, b: any) {
  const diff = a.sortIndex - b.sortIndex;

  return diff !== 0 ? diff : a.id - b.id;
}
